#include "headfiles.h"

using namespace std;

vector<int> findSubstring(string S, vector<string> &L) {
    int word_size = L[0].size();
    int word_num = L.size();
    vector<int> output;
    if (S.size() == 0 ||
        word_num == 0 ||
        word_size == 0) {
        return output;
    }

    // Not enough char, return empty        
    if (S.size() < word_num * word_size) {
        return output;
    }
    
    // Use a hash map to count the num of each word in L
    unordered_map<string, int> word_count;
    for (auto it = L.begin(); it != L.end(); it++) {
        word_count[*it]++;
    }
    
    int count, start;
    // Scan the string and count each found word.
    int index;
    for (int i = 0; i < word_size; i++) {
        unordered_map<string, int> fword;
        count = 0;
        start = i;
        for (index = i; index < S.size() - word_size; index += word_size) {
            string str = S.substr(index, word_size);
            auto wit = word_count.find(str);
            // Is a word in the dict
            if (wit != word_count.end()) {
                fword[str]++;
                count++;
                if (fword[str] <= word_count[str]) {
                    if (count == word_num) {
                        output.push_back(start);
                        string first_word = S.substr(start, word_size);
                        fword[first_word]--;
                        count--;
                        start += word_size;
                    }
                }
                else { // word_count is larger than required
                    while (fword[str] > word_count[str]) {
                        string str1 = S.substr(start, word_size);
                        auto it1 = word_count.find(str1);
                        if (it1 != word_count.end()) {
                            fword[str1]--;
                            count--;
                        }
                        start += word_size;
                    }
                }
            }
            else {
                fword.clear();
                count = 0;
                index += word_size;
                start = index;
            }
        }
    }
    
    return output;
}
